package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/5/11 17:02
 * @description ：从二叉搜索树中找到第n个元素
 * @modifiedBy ：
 */
public class KthSmallestSearcher {

    /**
     * 记录中序遍历过程中, 结点的位置
     */
    private int position=0;
    private int k = 0;
    private int result = 0;

    public int search(TreeNode node, int k) {
        this.k = k;
        traverse(node);
        return  result;
    }


    public void traverse(TreeNode node) {

        if (node == null) {
            return;
        }
        traverse(node.left);
        position++;
        if (position == k) {
            result = node.val;
        }
        traverse(node.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.left  = new TreeNode(3);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.left.left.left = new TreeNode(1);

        KthSmallestSearcher kthSmallestSearcher = new KthSmallestSearcher();
        kthSmallestSearcher.search(root, 3);
        System.out.println(kthSmallestSearcher.result);
    }

}
